1181 단어 정렬

"""max heap을 활용한 문제풀이
커스텀 `less` predicate은 금방 만들 수 있지만, 가장 중요한 정렬파트는 내가 직접
하나씩 구현해 보고 싶다."""

from dataclasses import dataclass
from typing import Any, List, Self, TypeVar, Type, Generic
from abc import ABCMeta, abstractmethod
from sys import stdin, stdout

standard_input = """13
but
i
wont
hesitate
no
more
no
more
it
cannot
wait
im
yours
"""


class Comparable(metaclass=ABCMeta):
    @abstractmethod
    def __lt__(self, other: Any) -> bool:
        # 제네릭 T 타입은 반드시 구현하여야 하는 메서드
        ...

    @abstractmethod
    def __init__(self):
        ...


T = TypeVar("T", bound=Comparable)


class Heap(Generic[T]):
    """완전이진트리로 구현된 힙. 인덱스는 보기 편하게 1부터 시작합니다. `__lt__`를 기준으로 minheap을 구축합니다."""

    data: List[T]

    @classmethod
    def parent(cls, i):
        return i >> 1

    @classmethod
    def left(cls, i):
        return i << 1

    @classmethod
    def right(cls, i):
        return (i << 1) + 1

    def __init__(self, t: Type[T]) -> None:
        self.data = [t()]  # 0번 인덱스는 사용안함

    def insert(self, item: T) -> None:
        data = self.data
        parent = Heap.parent

        data.append(item)

        # bubble up
        idx = len(data) - 1
        while parent(idx) > 0 and data[idx] < data[parent(idx)]:
            data[parent(idx)], data[idx] = data[idx], data[parent(idx)]
            idx = parent(idx)

    def pop(self) -> None:
        """루트 원소를 삭제하고 힙으로 다시 만든다"""
        if len(self) == 1:
            self.data.pop()
            return None
        if len(self) < 1:
            return None
        data = self.data
        left = self.left
        right = self.right

        # get last element root and bubble down
        data[1] = data.pop()

        idx = 1
        while left(idx) <= len(self):
            next_idx = 0
            if left(idx) == len(self):
                # right에 데이터가 없고 left가 마지막인 경우
                next_idx = left(idx)
            else:
                # 아래에 얼마나 더 내려가야 하는지 모르는 상황 → minheap 기준으로 작은 놈을 올려보내는 것이 상식
                if data[left(idx)] < data[right(idx)]:
                    next_idx = left(idx)
                else:
                    next_idx = right(idx)
            if data[next_idx] < data[idx]:
                # DO bubble down
                data[idx], data[next_idx] = data[next_idx], data[idx]
            else:
                # end bubble down
                break
            idx = next_idx

    def __len__(self) -> int:
        return len(self.data) - 1

    def peek(self) -> T | None:
        if len(self) == 0:
            return None
        return self.data[1]


@dataclass
class CustomComparable(Comparable):
    key: str

    def __lt__(self, other: Self) -> bool:
        if len(self.key) == len(other.key):
            return self.key < other.key
        return len(self.key) < len(other.key)

    def __init__(self, string=None):
        self.key = "" if string is None else string


if __name__ == "__main__":
    trash = input()
    heap = Heap(CustomComparable)
    for word in {e for e in stdin}:
        heap.insert(CustomComparable(word.strip()))
    while len(heap):
        value = heap.peek()
        heap.pop()
        if value:
            stdout.write(value.key + "\n")
        else:
            break